package java_core.array.Day5_13;

import java.util.ArrayList;
import java.util.List;

/*581. 最短无序连续子数组 https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
{1, 3, 2, 2, 2}   4
[1,3,2,3,3]  2
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ，所以升序的意思是<=。*/
public class ZuiDuanWuXvLianXvZiShuZu {
    public static void main(String[] args) {
        int[] arr = {2, 3, 3, 2, 4};
        System.out.println(findUnsortedSubarray(arr));
    }

    public static int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length == 1) {
            return 0;
        } else {
            int leftMax = 0;
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length-1; i++) {
                if (nums[i] >= nums[i + 1]) {
                    list.add(i);
                    leftMax = Math.max(leftMax, nums[i]);
                }
                if (leftMax > nums[i + 1]) {
                    list.add(i+1);
                }

            }
            int min = nums.length - 1;
            int max = 0;
            for (Integer integer : list) {
                if (integer < min) {
                    min = integer;
                }
                if (integer > max) {
                    max = integer;
                }
            }
            if (list.size() == 0) {
                return 0;
            }
            return max - min + 1;

        }

    }

    public class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int l = nums.length, r = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[j] < nums[i]) {
                        r = Math.max(r, j);
                        l = Math.min(l, i);
                    }
                }
            }
            return r - l < 0 ? 0 : r - l + 1;
        }
    }


}
